package com.mlh.dp.old;

// 题目：给你一个字符串 s，找到 s 中最长的回文子串。
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
// 举例：输入：s="babad"
// 输出："bab"
// 解释："aba"同样是符合题意的答案。

public class LongestPalindrome {
    public static void main(String[] args) {
        String s = "babadada";
        System.out.println(method3(s));
    }

    // 个人觉得这里用不了左神的方法
    // 核心思想：利用长度作为依据，长度为（i,j）的回文串需要满足两个条件
    // 第一：需要长度为（i+1,j-1）的子串是回文串，第二：需要位置 i 和 j的字符相同
    // 这里利用dp数组来记忆，降低时间复杂度
    public static String method1(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];// boolean默认值是false
        int sLen = s.length();
        int j;// 右边界
        int max = 0;
        int maxi = 0;
        int maxj = 0;
        for (int len = 1; len < s.length(); len++) {
            for (int i = 0; i < sLen; i++) {
                j = i + len - 1;
                if (j >= sLen) {
                    break;// 跳出单层循环
                }
                if ((len == 1 || len == 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    if (len > max) {
                        max = len;
                        maxi = i;
                        maxj = j;
                    }
                }
            }
        }
        String res = s.substring(maxi, maxj + 1);
        return res;
    }
    // 中心扩散法
    // 思想：很简单 遍历到一个字符，往两边做判断就可以

    // 马拉车算法
    public static String method2(String s) {
        int r = -1;// 右边界
        int l = -1;
        int[] res = new int[s.length() * 2 + 1];// 记录每个字符的最长回文串长度
        char[] newString = new char[s.length() * 2 + 1];
        int maxChar = -1;// 拥有最右回文半径的中心字符
        int maxLen = 0;// 最长回文串长度
        int resChar = -1;// 拥有最长回文半径的中心字符

        // 第一步：对字符串进行处理，加入特殊字符
        for (int i = 0; i < newString.length; i++) {
            if (i % 2 != 0) {
                newString[i] = s.charAt((i - 1) / 2);
            } else {
                newString[i] = 'a';
            }
        }
        // for(char temp:newString){
        //     System.out.print(temp+" ");
        // }

        // 第二步：按顺序遍历即可
        for (int i = 0; i < newString.length; i++) {
            //第一种情况：i>= r  直接暴力向两边做判断即可
            //第二种情况：i<r   又分为3种情况
            //(1)对称的i 其左边界在 l内 i的回文半径等于i'的回文半径
            //(2)对称的i 其左边界在 l上 以i为中心字符，从r处开始向外往两边扩
            //(3)对称的i 其左边界在 l外 i的回文半径等于r-i+1
            if (i >= r) {
                maxChar = i;
                r = find(newString, i);
                res[i] = (r - i) * 2 + 1;
                if (res[i] > maxLen) {
                    maxLen = res[i];
                    resChar = i;
                }
                l = i - (res[i]-1)/2;
            } else {
                int iLeft = maxChar - (i - maxChar);
                if (iLeft - res[iLeft]/2 > l) {
                    res[i] = res[iLeft];
                } else if (iLeft - res[iLeft]/2 == l) {
                    maxChar = i;
                    r = find(newString, i);
                    res[i] = (r - i) * 2 + 1;
                    if (res[i] > maxLen) {
                        maxLen = res[i];
                        resChar = i;
                    }
                    l = i - (res[i]-1)/2;
                } else {
                    res[i] = (r-i)*2+1;
                }

            }
        }

        if (resChar % 2 == 0) {
            return s.substring((resChar - 1) / 2 - (maxLen / 4) + 1, (resChar - 1) / 2 + (maxLen / 4) + 1);
        } else {
            return s.substring((resChar - 1) / 2 - (maxLen / 4), (resChar - 1) / 2 + (maxLen / 4) + 1);
        }


    }

    public static int find(char[] newString, int cur) {
        if (cur == newString.length - 1 || cur == 0) {
            return cur;
        }
        for (int i = cur + 1; i < newString.length; i++) {
            if (cur - (i - cur) >= 0) {
                if (newString[i] != newString[cur - (i - cur)]) {
                    return i - 1;
                }
            } else {
                return i - 1;
            }
        }
        return newString.length - 1;
    }

    // 马拉车算法
    public static String method3(String s) {
        int r = -1;//最右回文的右边界
        int l = -1;//最右回文的左边界
        int[] res = new int[s.length() * 2 + 1];// 记录每个字符的最长回文半径 包括中心字符
        char[] newString = new char[s.length() * 2 + 1];
        int maxChar = -1;// 拥有最右回文半径的中心字符
        int maxLen = 0;// 最长回文串半径
        int resChar = -1;// 拥有最长回文半径的中心字符

        // 第一步：对字符串进行处理，加入特殊字符
        for (int i = 0; i < newString.length; i++) {
            if (i % 2 != 0) {
                newString[i] = s.charAt((i - 1) / 2);
            } else {
                newString[i] = 'a';
            }
        }

        // 第二步：按顺序遍历即可
        for (int i = 0; i < newString.length; i++) {
            //第一种情况：i>= r  直接暴力向两边做判断即可
            //第二种情况：i<r   又分为3种情况
            //(1)对称的i 其左边界在 l内 i的回文半径等于i'的回文半径
            //(2)对称的i 其左边界在 l上 以i为中心字符，从r处开始向外往两边扩
            //(3)对称的i 其左边界在 l外 i的回文半径等于r-i+1
            if (i >= r) {
                maxChar = i;
                r = find2(newString, i,0);
                res[i] = r - i+ 1;
                if (res[i] > maxLen) {
                    maxLen = res[i];
                    resChar = i;
                }
            } else {
                l = maxChar - res[maxChar]+1;
                int sym_i = maxChar - (i - maxChar);
                int sym_iLeft=sym_i-res[sym_i]+1;
                if (sym_iLeft > l) {
                    res[i] = res[sym_i];
                } else if (sym_iLeft == l) {
                    maxChar = i;
                    r = find2(newString, i,r-i);
                    res[i] = r - i+ 1;
                    if (res[i] > maxLen) {
                        maxLen = res[i];
                        resChar = i;
                    }
                } else {
                    res[i] = r-i+1;
                }

            }
        }
        if (resChar % 2 == 0) { //因为加了特殊字符，因此返回时需要处理一下  同时主义substring（start,stop）不包括stop
            return s.substring((resChar - 1) / 2 - (maxLen / 2) + 1, (resChar + 1) / 2 + (maxLen / 2) );
        } else {
            return s.substring((resChar - 1) / 2 - ((maxLen-1) / 2), (resChar - 1) / 2 + ((maxLen-1) / 2) +1);
        }
    }

    //cur是中心字符
    //jump是可以跳过比较的字符数
    public static int find2(char[] newString, int cur,int jump) {
        if (cur == newString.length - 1 || cur == 0) {
            return cur;
        }
        for (int i = cur +jump+ 1; i < newString.length; i++) {
            if (cur - (i - cur) >= 0) {
                if (newString[i] != newString[cur - (i - cur)]) {
                    return i - 1;
                }
            } else {
                return i - 1;
            }
        }
        return newString.length - 1;
    }
}


